public class movingCount {
    public int _movingCount(int m, int n, int k) {
        if (k < 0)
            return 0;
        boolean[][] visited = new boolean[m][n];

        return dfs(m, n, 0, 0, k, visited);
    }

    public int dfs(int m, int n, int row, int col, int k, boolean[][] visited) {
        if (row < 0 || row >= m || col < 0 || col >= n || visited[row][col] || (numCount(row) + numCount(col)) > k)
            return 0;

        visited[row][col] = true;

        if (numCount(row) + numCount(col) <= k) {
            return 1 + dfs(m, n, row - 1, col, k, visited) + dfs(m, n, row, col - 1, k, visited)
                    + dfs(m, n, row + 1, col, k, visited) + dfs(m, n, row, col + 1, k, visited);
        }
        return 0;
    }

    public int numCount(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num = num / 10;
        }
        return sum;
    }
}
